package java学习.途虎养车;

import com.sun.source.tree.Tree;

import java.util.*;
import java.util.stream.Stream;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/8/31 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 多重背包 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 保养一辆车的最少油桶数
     * 1. dp[j] = min dp[j],dp[j-oils[i]]+1
     * 2. 初始化 最大值  组合数 先物品再背包
     * @param oils int整型一维数组
     * @param box int整型
     * @return int整型
     */
    public static int change (int[] oils, int box) {
        int[]dp = new int[box+1];
        Arrays.fill(dp, 100001);
        dp[0] = 0;
        for (int i = 0; i < oils.length; i++) {
            for (int j = oils[i]; j <=box ; j++) {
                dp[j] = Math.min(dp[j],dp[j-oils[i]]+1  );
            }
        }
//         System.out.println(Arrays.toString(dp));
        return  dp[box]==100001?-1:dp[box];
    }
    public int minimumIncompatibility (int[] nums, int k) {
        // write code here

        List<int[]> list = new ArrayList<>(Arrays.asList(nums));
        for (int[] ints : list) {
            for (int i = 0; i < ints.length; i++) {

            }
        }
        if(nums.length%k!=0){
            return -1;
        }else{

return 0;
        }

    }
    public static void main(String[] args) {
        int[] a = {1,2,5};
        System.out.println(change(a,11));
    }
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    int count = 0;
    public int numColor (TreeNode root) {
        // write code here
        if (root==null){
            return  0;
        }
        func(root);
        return count-2;
    }
    public void func(TreeNode n){

        if (n.left!=null){
            func(n.left);
        }
        if (n.left==null){
            count++;
        }
        System.out.println(n.val);

        if (n.right!=null){
            func(n.right);
        }
        if (n.right==null){
            count++;
        }
    }
    public int numColor2 (TreeNode root) {
        Set<TreeNode> set = new HashSet<TreeNode>();

        if (root==null){
            return  0;
        }
      return func(root,set);
    }
    public int func(TreeNode n,Set set){

        if (n.left!=null){
            set.add(n);
            func(n.left,set);
        }
        if (n.left==null){
           set.add(n);
        }
        if (n.right!=null){
            set.add(n);
            func(n.right,set);

        }
        if (n.right==null){
            set.add(n);
        }
        int size = set.size();
        if (set.contains(0)){
           size-=1;
        }
        return size;
    }
}
